# -*- coding:utf-8 -*-
# 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
# n<=39


class Solution:
    def Fibonacci(self, n):
        # write code here
        res = [0, 1, 1]
        while len(res) < n:
            res.append(res[-1]+res[-2])
        return res[n]

    def fibonacci_digui(self, n):
        if n == 0:
            return 0
        elif n == 1 or n == 2:
            return 1
        else:
            res = self.fibonacci_digui(n-1)+self.fibonacci_digui(n-2)
            return res

s = Solution()
print(s.fibonacci_digui(4))

